rtk 2007

2007.1.1

Poraba goriva

1. podnaloga

Del opreme sodobnega avtomobila je tudi potovalni računalnik. Zanj skrbi samostojni program, ki zajema podatke iz avtomobilskega informacijskega sistema in jih v obdelani obliki prikazuje na zaslončku. V našem primeru računalnik zajame, obdela in prikaže podatke enkrat na sekundo.

Eden od teh podatkov je povprečna poraba goriva. Predstavlja količino goriva, ki bi ga ob trenutni porabi potrebovali za prevoz stokilometrske razdalje. Ker pa izmerjena poraba med vožnjo zelo niha, potrebujemo podprogram, ki bo na podlagi meritev izračunal povprečno porabo v zadnjih desetih sekundah.

Naloga

Napiši podprogram povprecnaPoraba za izračun povprečne porabe.

Glavni program potovalnega računalnika ga bo poklical vsako sekundo in mu podal dva podatka - porabo goriva v zadnji sekundi (v litrih) in prevoženo pot v zadnji sekundi (v metrih). Ta dva podatka nista nikoli manjša od 0, tudi če se avtomobil vozi vzratno, je prevožena razdalja predstavljena z nenegativnim številom.

Tvoj podprogram mora vrniti povprečno porabo v zadnjih desetih sekundah, izraženo v porabljenih litrih goriva na 100 kilometrov. Če se avtomobil v zadnjih desetih sekundah sploh ni premaknil, naj tvoj podprogram vrne 0. Glavni program bo ta podatek prikazal na zaslonu potovalnega računalnika.

Vhodni podatki

Poraba goriva v zadnji sekundi (v litrih), prevožena razdalja v zadnji sekundi (v metrih). Oba podatka sta nenegativna in tipa float.

Izhodni podatki

Povprečna poraba v zadnjih desetih sekundah. Povprečna poraba je tipa float.

Opomba

Če hočeš, lahko uporabiš tudi globalne spremenljivke. Deklariraj jih izven funkcijskega podprograma povprecnaPoraba. Upoštevaš lahko, da so ob začetku delovanja vse globalne spremenljivke nastavljene na vrednost 0. Predpostavi, da je pred prvim klicem podprograma povprecnaPoraba avtomobil miroval in ni trošil goriva.

Uradna rešitev

poraba_goriva = [0] * 10
prevozena_pot = [0] * 10
zadnja_meritev = 0

def povprecnaPoraba(gorivo, razdalja):
    """Izračuna povprečno porabo goriva v zadnjih desetih sekundah."""
    # Najstarejšo meritev prepišemo z najnovejšo
    global zadnja_meritev
    global prevozena_pot
    global poraba_goriva
    zadnja_meritev = (zadnja_meritev + 1) % 10
    poraba_goriva[zadnja_meritev] = gorivo
    prevozena_pot[zadnja_meritev] = razdalja
    pot10s = 0
    poraba10s = 0
    for i in range(10):
        pot10s += prevozena_pot[i]
        poraba10s += poraba_goriva[i]
    pot10s = pot10s / 1000 / 100    # Osnovna enota za povprečno porabo so litri na 100 km
    if pot10s == 0:
        return 0
    else:
        return poraba10s / pot10s

2007.1.2

Hanojski stolpi

1. podnaloga

Hanojski stolpi so igra za enega igralca. Za igranje potrebujemo $n$ preluknjanih okroglih ploščic različnih premerov ter tri palice, na katere natikamo ploščice. Na začetku igre nataknemo vse ploščice na prvo palico in sicer tako, da so urejene po velikosti in je največja na dnu - dobimo nekakšno piramido. Cilj igre je, da celotno piramido prestavimo na tretjo palico, pri čemer moramo upoštevati pravila igre:

• V vsakem koraku smemo prestaviti le eno ploščico.
• Nikoli se ne sme zgoditi, da bi večja ploščica ležala na manjši.

Naloga

Napiši program, ki prebere neko stanje igre (torej: neko razporeditev ploščic na palicah) in izpiše, ali je takšno stanje ploščic dovoljeno in ali je končno. Stanje je dovoljeno, če pri njem nobena ploščica ne leži na neki manjši ploščici. Stanje je končno, če je dovoljeno in so vse ploščice na zadnji (tretji) palici.

Vhodni podatki

Stanje je opisano v štirih vrsticah: v prvi vrstici je število ploščic, recimo $n$ (ki je najmanj $1$ in največ $10$), v naslednjih treh vrsticah pa so opisi palic. Za vsako palico piše najprej število ploščic na njej, nato pa še velikosti teh ploščic (najmanjša ploščica ima velikost $1$, največja pa $n$); velikosti ploščic so navedene od spodaj navzgor - prva ploščica je tista, ki je na dnu palice, zadnja pa tista, ki je na vrhu.

Predpostaviš lahko, da se vsaka ploščica (od $1$ do $n$) pojavlja na natanko eni palici.

Izhodni podatki

Izpis ali je stanje dovoljeno in ali je stanje končno.

Primeri

Primer začetnega stanja igre s petimi ploščicami:

>>> 5
>>> 5 5 4 3 2 1
>>> 0
>>> 0
To stanje je dovoljeno, ni pa končno.

Še en primer s petimi ploščicami:

>>> 5
>>> 2 4 1
>>> 2 3 2
>>> 1 5
To stanje je dovoljeno, ni pa končno.

Primer nedovoljenega stanja:

>>> 5
>>> 3 4 1 2
>>> 0
>>> 2 5 3
To stanje ni niti dovoljeno niti končno.

Primer s sedmimi ploščicami:

>>> 7
>>> 0
>>> 0
>>> 7 7 6 5 4 3 2 1
To stanje je dovoljeno in končno.

Primer s tremi ploščicami:

>>> 3
>>> 0
>>> 0
>>> 3 1 2 3
To stanje ni niti dovoljeno niti končno.

Uradna rešitev

dovoljeno = True
koncno = True
n = int(input(''))
for palica in range(3):   # imamo 3 palice
    m = input('').split(' ')
    stevilo_ploscic_palica = int(m[0])
    if palica == 2 and stevilo_ploscic_palica != n:
        koncno = False   # Stanje je končno, če so vse ploščice na zadnji palici.
    prej_plosca = n + 1
    for i in range(1, stevilo_ploscic_palica + 1):
        plosca = int(m[i])
        if plosca > prej_plosca:
            dovoljeno = False
        if palica == 2 and plosca != n + 1 - i:
            koncno = False
        prej_plosca = plosca
if dovoljeno and koncno:
    print('To stanje je dovoljeno in končno.')
elif dovoljeno:
    print('To stanje je dovoljeno, ni pa končno.')
else:
    print('To stanje ni niti dovoljeno niti končno.')

2007.1.3

Ceste

1. podnaloga

Cestarji so pravkar dogradili več cest, ki vodijo iz nekega mesta v sosednje vasi. Na vsako cesto je treba na vsak kilometer postaviti tablico, ki označuje razdaljo od mesta.

Naloga

Napiši program, ki bo glede na število cest in njihove dolžine sestavil seznam potrebnih tablic. Vse ceste so dolge celo število kilometrov, tablic pa ne postavljamo na začetek in konec ceste.

Vhodni podatki

Program prebere podatke iz standardnega vhoda. Najprej prebere število cest, nato število novih cest in dolžine novih cest. Število cest in število novih cest uporabnik vpiše kot število, dolžine novih cest pa kot seznam števil, v katerem je na mestu $i-1$ dolžina $i$-te nove ceste (v kilometrih), pri čemer je dolžina ceste vsaj $1$.

Primer:

Število cest: 5
Od tega novih: 2
Dolžine: [4, 2]

Izhodni podatki

Program izpiše napise, katere tablice potrebujemo, in koliko teh potrebujemo.

Primer

Recimo, da imamo dve novi cesti, dolgi $4$ km in $2$ km. Potem potrebujemo naslednje tablice:

Napis na tablici: število takih tablic
1 km: 2
2 km: 1
3 km: 1

Z drugimi besedami, potrebujemo dve tablici z napisom '1 km', eno tablico z napisom '2 km' in eno tablico z napisom '3 km'.

Opomba

Naloga na tekmovanju je bila malo drugačna. Tekmovalec je lahko predpostavil, da sta na voljo funkciji st_cest in dolzina_ceste, vhodnih podatakov pa ni bilo treba brati. Funkcija st_cest vrne število novih cest, funkcija dolzina_ceste pa kot vhodni podatek vzame število nove ceste (če ceste oštevilčimo) in vrne dolžino i-te nove ceste.

Uradna rešitev

# Izračun novih tablic
st_cest = int(input('Število cest: '))
st_novih = int(input('Od tega novih: '))
import ast
dolzine_cest = ast.literal_eval(input('Dolžine: '))

tablice = st_cest * [0]   # Zaenkrat še ne vemo, če sploh potrebujemo kakšno tablico.
# Vemo pa, da je različnih tablic največ toliko, kolikor je cest.

for i in range(st_novih):
    for j in range(dolzine_cest[i] - 1):
        tablice[j] += 1

for i in range(len(tablice)):
    if tablice[i] != 0:
        print('{0} km: {1}'.format((i+1), tablice[i]))

2007.1.4

Zlogovna pisava

1. podnaloga

Zlogovna pisava je pisava, v kateri posamezni znaki praviloma ne predstavljajo posameznih glasov, pač pa cele zloge. Vendar pa takšna pisava ponavadi ne vsebuje po enega znaka za čisto vsak zlog, ki se v določenem jeziku pojavlja, ker bi to zahtevalo neugodno veliko znakov. Pogosto se omejimo samo na tiste zloge, ki so sestavljeni iz enega soglasnika in enega samoglasnika (v tem vrstnem redu). Na primer:

ta $= \prec$, te $= \bowtie$, pi $= \sqcap$, ru $= \approx$, sa $= \oslash$ in podobno.

Pri pretvarjanju besed iz latinice v kakšno drugo zlogovno pisavo pa naletimo na problem: nekaterih besed se ne da razdeliti na zloge te oblike (torej take, ki so sestavljeni iz dveh črk, od katerih je prva soglasnik in druga samoglasnik); tistim, ki se jih da, bomo rekli veljavne, ostalim pa neveljavne. Besedi kolo in teka sta na primer veljavni, besede kolut, tekma, in, obok in boa pa ne.

Če hočemo neko neveljavno besedo vendarle zapisati s takšno zlogovno pisavo, se lahko zatečemo k vrivanju dodatnih črk.

Naloga

Napiši podprogram koliko_crk, ki sprejme niz s in vrne število. Ta podprogram naj za dano besedo s pove, kolikšno je najmanjše število dodatnih črk, ki bi jih bilo treba vriniti v to besedo, da bi postala veljavna.

Vhodni podatki

Podprogram sprejme niz s. Predpostaviš lahko, da bo ta niz, ki ga bo kot parameter dobil tvoj podprogram, sestavljen samo iz malih črk angleške abecede (a, ..., z). Za samoglasnike veljajo črke a, e, i, o, u, ostale pa so soglasniki.

Izhodni podatki

Podprogram vrne število, ki predstavlja najmanjše število dodatnih črk, ki bi jih bilo treba vriniti v dano besedo, da bi postala veljavna.

Primer

V besedo oblak je treba vriniti najmanj tri črke: soglasnik na začetek, samoglasnik na konec in še en samoglasnik med b in l.

Uradna rešitev

def je_samoglasnik(char):
    """Vrne True, če je dana črka samoglasnik, sicer vrne False."""
    if char in 'aeiou':
        return True
    return False

def koliko_crk(s):
    """Izračuna in vrne število črk, ki jih moramo vriniti danemu nizu, da bo ta veljaven."""
    n = 0   # Števec vrinjenih črk
    s = 'a' + s + 'b'
    for i in range(len(s) - 1):
        if je_samoglasnik(s[i]) == je_samoglasnik(s[i+1]):
            n += 1
    return n

2007.1.5

Enačbe

1. podnaloga

Naloga

Napiši funkcijo, ki za nek dani niz preveri, če ta niz predstavlja veljavno enačbo. Enačba je veljavna natanko tedaj, ko ustreza naslednjim zahtevam:

• V enačbi smejo nastopati le števke ter znaka "$+$" in "$=$".
• Enačaj se mora pojavljati natanko enkrat. Levo in desno od njega mora biti v nizu vsaj po ena števka.
• Levo in desno od vsakega znaka "$+$" mora biti vsaj po ena števka.

Vhodni podatki

Niz poljubne dolžine.

Izhodni podatki

Funkcija vrne True, če vhodni niz predstavlja veljavno enačbo, in False sicer.

Primeri

Primeri nizov, ki predstavljajo veljavne enačbe:

• 1+2=456
• 12+34=40+3+2+01
• 12+3=1+23
• 123=103+20
• 0+00+000+00100=00000+000000

Primeri nizov, ki ne predstavljajo veljavnih enačb:

• 1+2=3=2+1
• 12=3*4
• a+1=1+a
• 12++3=15
• tralala
• 1 + 2 = 3
• abc123?
• 1+2+=3
• =
• +1+2=3

Opomba

Na tekmovanju je bilo treba zgolj opisati postopek in ne tudi napisati funkcije.

Komentar

Bodi pozoren na pogoje, kdaj je enačba veljavna.

Uradna rešitev

def je_veljavna(niz):
    """Preveri, če dani niz predstavlja veljavno enačbo. Vrne True,
    če da, sicer vrne False."""
    enacaj = False   # zaenkrat v nizu še nismo našli enačaja
    c = '+'   # predhoden znak, brez škode je to lahko +, saj se enačba ne sme začeti s +
    for i in range(len(niz)):
        if niz[i] == '=':
            if enacaj:
                return False
            elif c == '+':
                return False   # Enačaj na začetku ali za plusom
            else:
                enacaj = True
        elif niz[i] == '+':
            if (c == '+') or (c == '='):
                return False   # + mora biti za števko
        elif (niz[i] < '0') or (niz[i] > '9'):
            return False   # znak, ki ni niti števka niti plus niti enačaj
        c = niz[i]
    if not enacaj:
        return False   # enačba mora vsebovati enačaj
    if (c < '0') or (c > '9'):
        return False   # zadnji znak mora biti števka
    return True